package 动态规划;

public class MinclimbStairs {
		public static void main(String []args) {
			int [] cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1} ;
			int [] cost1 = {10, 15, 20};
			System.out.println(minClimbStairs(cost));
			System.out.println(minClimbStairs(cost1));
		}
	
	
	
	// 爬楼梯的额最小 花费 
	public static int minClimbStairs(int arr[]) {
		int N = arr.length;
		return process(arr,N);
	}
	public static int process(int arr[] , int rest) {
		if(arr.length == rest) {
			return Math.min(process(arr,rest-1)+arr[0],process(arr,rest-2)+arr[1]);
		}
		if(rest<=0) {
			return 0;
		}
		if(rest==1 || rest==2) {
			return arr[arr.length-rest];
		}
		int cost1=0;
		int cost2=0;
		cost1+=arr[arr.length-rest]+process(arr,rest-1);
		cost2+=arr[arr.length-rest]+process(arr,rest-2);
		return Math.min(cost1,cost2);
	}
}
	